package linklist;

/**
 * @author "随风Coding"
 * @email 1431471764@qq.com
 * @date 2025/8/14 16:07
 */
public class RemoveNthNodeFromEnd {

    /**
     * 删除链表的倒数第N个节点（修正版）
     *
     * @param head 链表头节点
     * @param n    倒数第N个节点（n≥1）
     * @return 删除后的链表头节点
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 处理边界：空链表或n无效
        if (head == null || n <= 0) {
            return head;
        }

        // 虚拟头节点（简化头节点删除逻辑）
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 快慢指针初始化（小写命名）
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指针先移动n+1步（确保慢指针最终指向倒数第n+1个节点）
        for (int i = 0; i <= n; i++) {
            if (fast == null) {
                return head; // n超过链表长度，无法删除，返回原链表
            }
            fast = fast.next;
        }

        // 快慢指针同步移动，直到快指针到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除目标节点（此时slow指向倒数第n+1个节点）
        if (slow.next != null) {
            slow.next = slow.next.next;
        }

        return dummy.next;
    }

    // ------------------------------ 测试方法 ------------------------------
    public static void main(String[] args) {
        // 测试用例1：正常情况（删除中间节点）
        ListNode head1 = createList(new int[]{1, 2, 3, 4, 5});
        int n1 = 2;
        ListNode result1 = removeNthFromEnd(head1, n1);
        printList(result1); // 预期输出：1->2->3->5

        // 测试用例2：删除头节点（链表长度等于n）
        ListNode head2 = createList(new int[]{1, 2, 3});
        int n2 = 3;
        ListNode result2 = removeNthFromEnd(head2, n2);
        printList(result2); // 预期输出：2->3

        // 测试用例3：删除尾节点（n=1）
        ListNode head3 = createList(new int[]{1, 2, 3});
        int n3 = 1;
        ListNode result3 = removeNthFromEnd(head3, n3);
        printList(result3); // 预期输出：1->2

        // 测试用例4：链表只有一个节点（删除后为空）
        ListNode head4 = createList(new int[]{1});
        int n4 = 1;
        ListNode result4 = removeNthFromEnd(head4, n4);
        printList(result4); // 预期输出：null

        // 测试用例5：空链表输入
        ListNode head5 = null;
        int n5 = 1;
        ListNode result5 = removeNthFromEnd(head5, n5);
        printList(result5); // 预期输出：null

        // 测试用例6：n大于链表长度（返回原链表）
        ListNode head6 = createList(new int[]{1, 2});
        int n6 = 3;
        ListNode result6 = removeNthFromEnd(head6, n6);
        printList(result6); // 预期输出：1->2
    }

    // 辅助方法：根据数组创建链表
    private static ListNode createList(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int num : nums) {
            current.next = new ListNode(num);
            current = current.next;
        }
        return dummy.next;
    }

    // 辅助方法：打印链表
    private static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print("->");
            }
            current = current.next;
        }
        System.out.println();
    }

    // 链表节点定义（静态内部类）
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}